# conding=utf-8
import logging
import struct
import copy
import time
from datetime import datetime
from operator import attrgetter
from ryu.base import app_manager
from ryu.controller import ofp_event
from ryu.controller.handler import MAIN_DISPATCHER, DEAD_DISPATCHER
from ryu.controller.handler import CONFIG_DISPATCHER
from ryu.controller.handler import set_ev_cls
from ryu.ofproto import ofproto_v1_0
from ryu.ofproto import ether
from ryu.lib.packet import packet
from ryu.lib.packet import ethernet
from ryu.lib.packet import ipv4
from ryu.lib.packet import arp
from ryu.lib.ip     import ipv4_to_bin
from ryu.lib import addrconv
from ryu.lib import hub
from ryu.lib import ip
import ryu.networkx as nx

SLEEP_PERIOD = 1

# User defined packet format
PREAMBLE = 'aa:aa:aa:aa:aa:aa'

TYPE_SET_TOPOLOGY       = 0x88aa
TYPE_GET_TOPOLOGY       = 0x88bb
TYPE_UPDATE_TOPOLOGY    = 0x88cc
TYPE_SET_FLOWTABLE      = 0x88dd
TYPE_Multicast_Jion     = 0x88ee


# TYPE_GET_TOPOLOGY pakcet definition
HEADER_SIZE = 12
SWITCH_SIZE = 8
HOST_SIZE = 6

Priority_Level1 = 1
Priority_Level2 = 2

OFPFC_ADD = 0               # New flow.
OFPFC_MODIFY = 1            # Modify all matching flows.


def convert_ip_to_int(ip):
    '''
    From string to int
    10.0.0.2 -> 167772162
    '''
    tmp = 0
    for b in ipv4_to_bin(ip):
        tmp |= ord(b)
        tmp = tmp << 8
    tmp = tmp >> 8
    return tmp


class ClassName(object):
    """docstring for ClassName"""
    def __init__(self, arg):
        super(ClassName, self).__init__()
        self.arg = arg
        
class Network_Aware(app_manager.RyuApp):
    OFP_VERSIONS = [ofproto_v1_0.OFP_VERSION]
    _NAME = 'network_aware'

    def __init__(self, *args, **kwargs):
        super(Network_Aware, self).__init__(*args, **kwargs)
        self.name = "Network_Aware"

        self.dps = {}           # datapath_id => Datapath class

        self.link_to_port = {}  # links :(src_dpid,dst_dpid)->(src_port,dst_port)
        self.access_table = {}  # {(dpid,port)->host_ip}

        self.edge_sw = []       # ToR switch id
        self.core_sw = []       # Core switch id, use for multi layer network

        '''
        edge attributes: 'port': [(src_port,dst_port),...,(src_port,dst_port)] one edge has multi-port means that has higher bandwidth
        node attributes: 'host': [(port,host_ip),...,(port,host_ip)]
        port num [1:k]
        '''
        self.whole_graph    = nx.DiGraph()  # Including all the information of the network, host and switch
        self.static_graph   = nx.DiGraph()  # Reserve a static, connected channel in the network
        self.static_degree  = 2             # The static graph, which links are no reconfigurable, from port1 to port static_degree
        
        # Multicast Address ---> {dpid1:[port1,port2,port3],...,dpid n:[port1,port2,..])}
        # The first dpid1,port1 means the sender hosts, and the other means the recivers
        self.multicast_groups = {}
        self.multicast_groups['10.0.0.254'] = {3:[1,2,3,4], 4:[1,2,3,4], 5:[1,2,3,4], 6:[1,2,3,4], 7:[1,2,3,4]}

        self.discover_thread = hub.spawn(self._discover)

    def _discover(self):
        j = 0
        while True:
            if j == 10:
                print "%s Initial the network" %j
                self.Initial()
            if j == 20:
                print "%s reconfigure_regular_graph" %j
                self.reconfigure_regular_graph()
    
            hub.sleep(SLEEP_PERIOD)
            j = j + 1

    @set_ev_cls(ofp_event.EventOFPSwitchFeatures, CONFIG_DISPATCHER)
    def switch_features_handler(self, ev):
        datapath = ev.msg.datapath
        self.dps[datapath.id] = datapath
        self.logger.info("switch:%s connected", datapath.id)

    def Initial(self):
        self.set_topology()
        print "set_topology"
        time.sleep(0.01)
        self.get_topology()
        print "get_topology"
        time.sleep(0.01)
        self.static_graph = self.sub_copy(self.whole_graph, 1, self.static_degree)
        self.show_topology(self.whole_graph)
        self.show_topology(self.static_graph)
        self.set_flowtable(1,0)
        time.sleep(0.000001)
        self.calculate_routing(self.static_graph, OFPFC_ADD, Priority_Level1, 1)
        self.install_last_hop_flows(self.whole_graph, Priority_Level1)
        time.sleep(0.000001)
        self.set_flowtable(0,0)
        self.calculate_routing(self.static_graph, OFPFC_ADD, Priority_Level1, 1)
        self.install_last_hop_flows(self.whole_graph, Priority_Level1)


    def set_topology(self): # Initial the neighbours of the data plane
        self.logger.info("set_topology")
        pkt_data = bytearray(8)
        struct.pack_into("!6sH", pkt_data, 0, addrconv.mac.text_to_bin(PREAMBLE), TYPE_SET_TOPOLOGY)

        for dp in self.dps.itervalues():
            actions = [dp.ofproto_parser.OFPActionOutput(dp.ofproto.OFPP_CONTROLLER)]
            dp.send_packet_out(actions=actions, data=pkt_data)
    
    def get_topology(self):
        self.logger.info("get_topology")
        pkt_data = bytearray(8)
        struct.pack_into("!6sH", pkt_data, 0, addrconv.mac.text_to_bin(PREAMBLE), TYPE_GET_TOPOLOGY)

        for dp in self.dps.itervalues():
            actions = [dp.ofproto_parser.OFPActionOutput(dp.ofproto.OFPP_CONTROLLER)]
            dp.send_packet_out(actions=actions, data=pkt_data)
    
    def set_flowtable(self, wFlowTable_id, rFlowTable_id):
        '''
        # Frame Format
        # 6 MAC ADDR :'aa:aa:aa:aa:aa:aa'
        # 2 Type : TYPE_SET_FLOWTABLE
        # 1 m_wFlowTable : 0:m_comFlowTable 1:m_midFlowTable
        # 1 m_rFlowTable : 0:m_comFlowTable 1:m_midFlowTable
        '''
        self.logger.info("set_flowtable")
        pkt_data = bytearray(10)
        struct.pack_into("!6sHBB", pkt_data, 0, addrconv.mac.text_to_bin(PREAMBLE), TYPE_SET_FLOWTABLE, wFlowTable_id, rFlowTable_id)

        for dp in self.dps.itervalues():
            actions = [dp.ofproto_parser.OFPActionOutput(dp.ofproto.OFPP_CONTROLLER)]
            dp.send_packet_out(actions=actions, data=pkt_data)

    def reconfigure_regular_graph(self):
        self.logger.info("reconfigure_regular_graph")
        degree = self.whole_graph.degree(1)/2 - self.static_degree
        nodes = len(list(self.whole_graph.nodes()))
        regular_graph = nx.Graph(nx.random_regular_graph(degree,nodes)) #node id starts from 0
        while not nx.is_connected(regular_graph):
            regular_graph = nx.Graph(nx.random_regular_graph(degree,nodes))

        match_results = {}
        match_results = self.bipartite_matchings(regular_graph, 3)
        self.set_flowtable(0, 1)
        self.update_topology(match_results)
        self.whole_graph = self.update_graph(self.static_graph, match_results)
        self.show_topology(self.whole_graph)
        self.calculate_routing(self.whole_graph, OFPFC_MODIFY, Priority_Level1, 1)
        self.set_flowtable(0, 0)
        
    
    def bipartite_matchings(self, graph, port_base):
        '''
        Calculate k matchings
        This method is not efficient, the time complexity is :
        '''
        self.logger.info("bipartite_matchings")
        # Transform the graph to bipartite graph
        bipartite_src = []
        bipartite_dst = []
        bipartite_edge = []
        base = len(list(graph.nodes()))
        for i in list(graph.nodes()):
            bipartite_src.append(i+1)
            bipartite_dst.append(i+1+base)
            for j in list(graph.neighbors(i)):
                bipartite_edge.append((i+1, j+1+base))
        bipartite_graph = nx.Graph()
        bipartite_graph.add_nodes_from(bipartite_src, bipartite=0)
        bipartite_graph.add_nodes_from(bipartite_dst, bipartite=1)
        bipartite_graph.add_edges_from(bipartite_edge)

        # Decompose the graph to k matchings
        match_results = {} # port num: matching
        starttime = datetime.now()
        for x in range (port_base, bipartite_graph.degree(1)+port_base):
            match = nx.bipartite.maximum_matching(bipartite_graph)
            temp_match = []
            for i,j in match.items():
                if i > base:
                    break       
                temp_match.append((i,j-base))
                if (i,j) in bipartite_graph.edges():
                    bipartite_graph.remove_edge(i,j)
            match_results[x] = temp_match
        endtime = datetime.now()
        timediff = endtime - starttime
        print 'matching time %d.' %timediff.seconds,'%ds' %timediff.microseconds

        if False:
            for x in match_results.keys():
                print "match %d" %x
                print match_results[x]
        return match_results

    def update_topology(self, matchings):
        '''
        # Configure the circuits
        # Frame Format
        # 6 MAC ADDR :'aa:aa:aa:aa:aa:aa'
        # 2 Type : TYPE_UPDATE_TOPOLOGY
        # 2 circuit num : n
        # 4 <src_portNum, dst_datapathID> 1
        #   ....
        # 4 <src_portNum, dst_datapathID> n
        '''
        self.logger.info("update_topology")
        self.link_to_port.clear()
        for datapath in self.dps.itervalues():
            size = 10 + 4 * len(matchings)
            pkt_data = bytearray(size)
            struct.pack_into("!6sHH", pkt_data, 0, addrconv.mac.text_to_bin(PREAMBLE), TYPE_UPDATE_TOPOLOGY, len(matchings))
            counter = 0
            for port in matchings.keys():
                src_portNum = port
                dst_portNum = port
                for match_tuple in matchings[port]:
                    if datapath.id == match_tuple[0]:
                        dst_datapathID = match_tuple[1]
                        break
                struct.pack_into("!HH", pkt_data, 10+counter*4, src_portNum, dst_datapathID)
                counter = counter + 1

                self.link_to_port[(datapath.id, dst_datapathID)] = (src_portNum, dst_portNum)
            actions = [datapath.ofproto_parser.OFPActionOutput(datapath.ofproto.OFPP_CONTROLLER)]
            datapath.send_packet_out(actions = actions, data = pkt_data)

    def calculate_routing(self, graph, flow_command, priority=Priority_Level1, cutoff=1):
        '''
        k-shortest routing, multi-path
        '''
        self.logger.info("calculate_routing")
        starttime = datetime.now()
        for sw_src in list(graph.nodes()):
            for sw_dst in list(graph.nodes()):
                path_results = []
                if sw_dst != sw_src:
                    path_results = list(nx.all_simple_paths(graph, source=sw_src, target=sw_dst, cutoff=cutoff))

                    tmp_cutoff = cutoff
                    while len(path_results) == 0 :
                        tmp_cutoff = tmp_cutoff + 1
                        path_results = list(nx.all_simple_paths(graph, source=sw_src, target=sw_dst, cutoff=tmp_cutoff))

                    self.logger.info(path_results)
                    for host_tuple in graph.node[sw_dst]['host']:
                        self.logger.info("sw_src:%s --> sw_dst:%s host_dst:%s" % (sw_src, sw_dst, host_tuple[1]))
                        flow_info = (ether.ETH_TYPE_ARP, host_tuple[1], priority) # ARP Flow
                        self.install_flows(path_results, flow_info, flow_command)
                        #time.sleep(0.000000001)
                        flow_info = (ether.ETH_TYPE_IP, host_tuple[1], priority) # IP Flow
                        self.install_flows(path_results, flow_info, flow_command)
                        #time.sleep(0.000000001)
        endtime = datetime.now()
        timediff = endtime - starttime
        print 'calculate routing time %d.' %timediff.seconds,'%ds' %timediff.microseconds

    def install_flows(self, path, flow_info, flow_command):
        '''
        multi-path
        path = [[dpid1, dpid2,...,dpidn],[dpid1, dpid3,...,dpidn],...,[dpid1, dpidk,...,dpidn]]
        flow_info = (eth_type, dst_ip, priority)
        '''
        self.logger.info("install_flows")
        assert path
        # first flow entry
        datapath = self.dps[path[0][0]]
        ofproto = datapath.ofproto
        parser = datapath.ofproto_parser
        out_port = ofproto.OFPP_LOCAL

        # Filter the pathes, the next_sw may be same in diff pathes
        # Such as [[1, 11, 7, 10], [1, 11, 9, 10], [1, 12, 9, 10]]
        src_sw = path[0][0]
        next_swtiches = []
        for path_i in xrange(0,len(path)):
            if path[path_i][1] not in next_swtiches:
                next_swtiches.append(path[path_i][1])

        actions = []
        for path_i in xrange(0,len(next_swtiches)):
            next_sw = next_swtiches[path_i]
            out_port_list = self.get_link2port(src_sw, next_sw)
            for x in xrange(0,len(out_port_list)):
                self.logger.info("count:%s  src_sw:%s --> next_sw:%s  outport: %s" %(x, src_sw, next_sw, out_port_list[x][0]))
                actions.append(parser.OFPActionOutput(out_port_list[x][0]))

        match = parser.OFPMatch(
            dl_type = flow_info[0],
            nw_dst = convert_ip_to_int(flow_info[1]))

        if flow_command == OFPFC_ADD:
            command = ofproto.OFPFC_ADD
        else:
            command = ofproto.OFPFC_MODIFY
        
        self.flow_mod(datapath, flow_info[2], match, command, actions)

    def install_last_hop_flows(self, graph, priority=Priority_Level1):
        self.logger.info("install_last_hop_flows")
        for sw in list(graph.nodes()):
            datapath = self.dps[sw]
            ofproto = datapath.ofproto
            parser = datapath.ofproto_parser
            out_port = ofproto.OFPP_LOCAL

            for host in self.whole_graph.node[sw]['host']:
                outport = host[0]
                nw_dst = host[1]
                self.logger.info("outport:%s ---> host_ip: %s" %(outport, nw_dst))
                actions = [parser.OFPActionOutput(outport)]
                match = parser.OFPMatch(
                    dl_type = ether.ETH_TYPE_ARP,
                    nw_dst = convert_ip_to_int(nw_dst))
                self.flow_mod(datapath, priority, match, ofproto.OFPFC_ADD, actions)

                match = parser.OFPMatch(
                    dl_type = ether.ETH_TYPE_IP,
                    nw_dst = convert_ip_to_int(nw_dst))
                self.flow_mod(datapath, priority, match, ofproto.OFPFC_ADD, actions)

    def flow_mod(self, datapath, p, match, command, actions, idle_timeout=0, hard_timeout=0):
            ofproto = datapath.ofproto
            parser = datapath.ofproto_parser

            mod = parser.OFPFlowMod(
                datapath=datapath, match=match, cookie=0,
                command=command, idle_timeout=idle_timeout, hard_timeout=hard_timeout,
                priority=p,
                flags=ofproto.OFPFF_SEND_FLOW_REM, actions=actions)
            
            datapath.send_msg(mod)

    def get_link2port(self, src_dpid, dst_dpid):
        if (src_dpid, dst_dpid) in list(self.whole_graph.edges()):
            return self.whole_graph.edge[src_dpid][dst_dpid]['port']
        else:
            self.logger.debug("Link to port is not found.")
            return None

    def sub_copy(self, graph, cutoff_l = 0, cutoff_h = 0):
        '''
        copy the graph that the attributes "port" attributes of each edge is in [cutoff_l, cutoff_h]
        cutoff_l = cutoff_h means copy all the graph.
        '''
        sub_graph = nx.DiGraph()
        if cutoff_l == cutoff_h:
            sub_graph = graph.copy()
        else:
            for sw_src in list(graph.nodes()):
                sub_graph.add_node(sw_src, host = graph.node[sw_src]['host'])
                for sw_dst in list(graph.nodes()):
                    if (sw_src, sw_dst) in list(graph.edges()):
                        port_list = []
                        edge_port = graph.edge[sw_src][sw_dst]['port']
                        for port_tuple in edge_port:
                            if port_tuple[0] >= cutoff_l and port_tuple[0] <= cutoff_h:
                                port_list.append(port_tuple)
                        if port_list:
                            sub_graph.add_edge(sw_src, sw_dst, port= port_list)
        return sub_graph

    def update_graph(self, graph, matchings):
        '''
        update the graph based on the new matchings
        '''
        for x in matchings.keys():
            print "match %d" %x
            print matchings[x]
            for k in matchings[x]:
                print k

        new_graph = graph.copy()
        for port in matchings.keys():
            src_portNum = port
            dst_portNum = port
            for match_tuple in matchings[port]:
                if match_tuple not in list(new_graph.edges()):
                    new_graph.add_edge(match_tuple[0], match_tuple[1], port = [(src_portNum, dst_portNum)])
                elif (src_portNum, dst_portNum) not in new_graph[match_tuple[0]][match_tuple[1]]['port']:
                    new_graph[match_tuple[0]][match_tuple[1]]['port'].append(((src_portNum, dst_portNum)))

        return new_graph

    def merge(self, graph_dst, graph_src, cutoff_l = 0, cutoff_h = 0):
        '''
        merge the graph_src into the graph_dst
        '''
        merge_graph = nx.DiGraph()
        for sw_src in graph_src:
            for sw_dst in graph_dst:
                if (sw_src, sw_dst) in list(graph_src.edges()):
                    edge_port_src = graph_src.edge[sw_src][sw_dst]['port']
                    edge_port_dst = graph_dst.edge[sw_src][sw_dst]['port']
                    edge_port = []
                    for ports in edge_port_dst:
                        if ports[0] >= cutoff_l and ports[0] <= cutoff_h:
                            edge_port.append(ports)

                    for ports in edge_port_src:
                        if ports not in edge_port:
                           edge_port.append(ports)
                    if edge_port:
                        merge_graph.add_edge(sw_src,sw_dst, port=edge_port)
        return merge_graph

    # Frame Format
    # 6 MAC ADDR :'aa:aa:aa:aa:aa:aa'
    # 2 Type : TYPE_GET_TOPOLOGY
    # 2 switch link num : m
    # 2 host link num : n
    # 8 <src_portNum, dst_portNum, dst_datapathID> 1
    #   ....
    # 8 <src_portNum, dst_portNum, dst_datapathID> m
    # 6 <src_portNum, Ipv4Address> 1
    #   ....
    # 6 <src_portNum, Ipv4Address> n
    @set_ev_cls(ofp_event.EventOFPPacketIn, MAIN_DISPATCHER)
    def _packet_in_handler(self, ev):
        msg = ev.msg
        datapath = msg.datapath

        parser = datapath.ofproto_parser
        in_port = msg.in_port
        pkt = packet.Packet(msg.data)

        preamble_bin, pkt_type = struct.unpack_from("!6sH", pkt.data)
        preamble = addrconv.mac.bin_to_text(preamble_bin)

        if preamble == PREAMBLE: # user defined packet
            if pkt_type == TYPE_GET_TOPOLOGY: # undirectional links

                (switch_link_num, host_link_num) = struct.unpack_from("!HH", pkt.data, 8)
                
                for x in xrange(0,switch_link_num):
                    (src_portNum, dst_portNum, dst_datapathID) = struct.unpack_from("!HHI", pkt.data, HEADER_SIZE+x*SWITCH_SIZE)
                    self.link_to_port[(datapath.id, dst_datapathID)] = (src_portNum, dst_portNum)
                    
                    if (datapath.id, dst_datapathID) not in list(self.whole_graph.edges()):
                        self.whole_graph.add_edge(datapath.id, dst_datapathID, port = [(src_portNum, dst_portNum)])
                    elif (src_portNum, dst_portNum) not in self.whole_graph[datapath.id][dst_datapathID]['port']:
                        self.whole_graph[datapath.id][dst_datapathID]['port'].append(((src_portNum, dst_portNum)))

                    if host_link_num == 0 and datapath.id not in self.core_sw:
                        self.core_sw.append(datapath.id)

                host_list = []
                for x in xrange(0,host_link_num):
                    (src_portNum, host_ip) = struct.unpack_from("!H4s", pkt.data, HEADER_SIZE+switch_link_num*SWITCH_SIZE+x*HOST_SIZE)
                    self.access_table[(datapath.id, src_portNum)] = ip.ipv4_to_str(host_ip)
                    host_list.append((src_portNum,ip.ipv4_to_str(host_ip)))
                    if datapath.id not in self.edge_sw:
                        self.edge_sw.append(datapath.id)
                self.whole_graph.add_node(datapath.id, host = host_list)


    def show_topology(self, graph, topo = True, link = True, host = True):
        #directed k regular graph, egress and ingress degree are equal and all nodes' degree are equal
        degree = graph.degree(1)/2
        print "topology degree %d" % degree
        print "topology diameter %s" % nx.diameter(graph)
        switch_num = len(graph)
        if topo:
            print "---------------------Topo Link---------------------"
            print '%4s' % ("switch"),
            for sw in list(graph.nodes()):
                print '%3d' % sw,
            print ""
            
            for sw_src in list(graph.nodes()):
                print '%6d' % sw_src,
                for sw_dst in list(graph.nodes()):
                    if sw_src == sw_dst:
                        print '%3s' % "0",
                    elif (sw_src, sw_dst) in list(graph.edges()):
                        if graph.edge[sw_src][sw_dst]['port']:
                            print '%3s' % "1",
                        else:
                            print '%3s' % "*",
                    else:
                        print '%3s' % "*",
                print ""

        # show link
        if link:
            print "---------------------Link Port---------------------"
            print '%2s' % ("switch"),
            for sw in list(graph.nodes()):
                print '%4d' % sw,
            print ""
            for sw_src in list(graph.nodes()):
                print '%6d' % sw_src,
                for sw_dst in list(graph.nodes()):
                    if (sw_src, sw_dst) in list(graph.edges()):
                        if graph.edge[sw_src][sw_dst]['port']:
                            print '%s' % "[",
                            for port_tuple in graph.edge[sw_src][sw_dst]['port']:
                                print '%s' % str(port_tuple[0]), #if has multi port, only show the first port
                            print '%s' % "]",
                        else:
                            print '%3s' % "[]",
                    else:
                        print '%3s' % "[]",
                print ""

        # show host
        if host:
            print "----------------Access Host-------------------"
            print '%10s' % ("switch"), '%12s' % "Host"

            for sw in list(graph.nodes()):
                for host in graph.node[sw]['host']:
                    print '%10d:    ' % sw, host[1]